The invention relates generally to communication systems and, more particularly, to decoding techniques for use in such systems.
Convolutional codes and bandwidth efficient Trellis Coded Modulation (TCM) are widely used in many different types of communication systems, including voice-band modems, Asymmetric Digital Subscriber Line (ADSL) systems, audio broadcasting systems, Fast or Gigabit Ethernet systems, cellular systems and wireless local loop systems. Convolutional codes are described in, e.g., G. C. Clark, Jr. and J. B. Cain, xe2x80x9cError Control Coding for Digital Communications,xe2x80x9d New York: Plenum, 1981, and TCM is described in, e.g., G. Ungerboeck, xe2x80x9cTrellis-coded modulation with redundant signal sets part I,xe2x80x9d IEEE Communications Magazine, Vol. 25, February 1987, and G. Ungerboeck, xe2x80x9cTrellis-coded modulation with redundant signal sets part II,xe2x80x9d IEEE Communications Magazine, Vol. 25, February 1987.
The Viterbi algorithm is an efficient maximum-likelihood sequence detection method for decoding convolutional and trellis codes transmitted over Additive White Gaussian Noise (AWGN) channels. The Viterbi algorithm is described in, e.g., A. J. Viterbi, xe2x80x9cError Bounds for Convolutional Codes and an Asymptotically Optimum Decoding Algorithm,xe2x80x9d IEEE Trans. on Information Theory, Vol. IT-13, April 1967, G. D. Forney, Jr., xe2x80x9cMaximum-likelihood sequence detection in the presence of intersymbol interference,xe2x80x9d IEEE Trans. on Information Theory, Vol. IT-18, pp. 363-378, May 1972, and G. D. Forney, Jr., xe2x80x9cThe Viterbi algorithm,xe2x80x9d IEEE Proceedings, Vol. 61, pp. 268-278, March 1973. The Viterbi algorithm is currently used, almost exclusively, for decoding these codes in all practical applications. It is also known that for Rayleigh fading channels, if the Channel State Information (CSI) is known, the Viterbi Algorithm can still be the optimum detection method for detecting these codes, with minor modifications, as described in, e.g., E. Biglieri, D. Divsalar, P. J. McLane and M. K. Simon, xe2x80x9cIntroduction to Trellis-Coded Modulation with Applications,xe2x80x9d New York, N.Y.: Macmillan Publishing Company, 1991.
The Viterbi algorithm finds the most-likely codeword sequence in a code, as described by a trellis diagram, given a particular sequence of noisy symbols at the channel output. It is an application of dynamic programming and the search for the optimum path is done recursively. In the Viterbi algorithm for decoding convolutional and trellis codes, square Euclidean distance is the optimum branch metric for decoding sequences transmitted in AWGN channels and in Rayleigh fading channels when CSI is appropriately included.
Multiplications are generally required in the Viterbi algorithm only to compute the square Euclidean distances to obtain branch metrics associated with branches of the trellis. Look-up tables may also be used to obtain the square Euclidean distances. Depending on the trellis to be implemented, a typical look-up table can have a size of at least 29xc3x979xcx9c4 k bits. For high bit-rate applications, parallel branch metric computations may be required. Duplications of multipliers or look-up tables to implement parallel branch metric computation can increase the decoder complexity tremendously, making such arrangements prohibitive for high bit-rate applications. Furthermore, the multipliers and the delay associated with accessing large look-up tables can become a processing bottleneck for a fully pipelined Viterbi decoder in high bit-rate applications.
As an alternative, absolute distances have been proposed for use as branch metrics. However, the use of absolute distances as branch metrics has the undesirable effect of reducing the performance of the Viterbi decoder. See H. Lou, xe2x80x9cImplementing the Viterbi algorithm. Fundamentals and real-time issues for processor designers,xe2x80x9d IEEE Signal Processing Magazine, Vol. 12, pp. 42-52, September 1995.
A need therefore exists for a more efficient branch metric representation, which simplifies the decoder without compromising its performance.
The present invention provides an improved branch metric representation, based on linear distances, that overcomes the above-described decoder complexity problems of the prior art, while simultaneously avoiding any significant degradation in decoder performance.
An illustrative embodiment of the invention for decoding a sequence of received symbols includes a branch metric calculation unit, an add-compare-select unit, and a traceback unit. The branch metric unit computes branch metrics associated with transitions between states of a multi-stage trellis representation of a state machine. In accordance with the invention, each of the branch metrics correspond to a linear distance between a given one of the received symbols and its nearest codeword in a given stage of the trellis. The add-compare-select unit utilizes the branch metrics of a current stage, along with a previously-generated path metric, for comparison purposes in determining a survivor path and corresponding updated path metric for a current stage of the multi-stage trellis. The traceback unit utilizes the updated path metric to generate a corresponding decoded output.
Advantageously, the decoder is configured such that it achieves a level of performance using the linear distance branch metrics which is equivalent to that achieved using squared distance branch metrics, while the decoder complexity is reduced through the elimination of multiplication operations. More particularly, the invention allows adders rather than multipliers or large look-up tables to be used to obtain the branch metrics, thereby considerably simplifying the decoder. The techniques of the invention are suitable for use with convolutional and trellis codes for a variety of different modulation constellations, such as, e.g., QPSK (Quadrature Phase Shift Keying), 8-PSK (Phase-Shift-Keying), 16-QAM (Quadrature Amplitude Modulation), 32-QAM and larger constellations.